package m202406.d10;

/**
 * @@author: 爱做梦的锤子
 * @date: 2024/6/10 11:24
 */
public class Q42 {

    /**
     * 0 0 1 1 2 2 2 2 3 3 3 3  left
     * 3 3 3 3 3 3 3 2 2 2 1 0  right
     * @param args
     */
    public static void main(String[] args) {
        Q42 q42 = new Q42();
        q42.trap(new int[]{0, 1, 0, 2, 1, 0, 1, 3, 2, 1, 2, 1});
    }

    public int trap(int[] height) {
        int n = height.length;
        int[] maxLeft = new int[n];
        int[] maxRight = new int[n];
        int max = height[0];
        for (int i = 1; i < n; i++) {
            max = Math.max(max, height[i - 1]);
            maxLeft[i] = max;
        }
        max = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            max = Math.max(max, height[i + 1]);
            maxRight[i] = max;
        }

        int res = 0;
        for (int i = 0; i < n; i++) {
            res =res + Math.max(0, Math.min(maxLeft[i], maxRight[i]) - height[i]);
        }
        return res;
    }
}
